const arr = [1, 0, 1, 1, 4, 0, 0, 2];
const moveZero2End = (arr: Array<number>) => {
  const len = arr.length;
  if (len === 0) return;
  // 数组中0元素的长度
  let zeroLenght: number = 0;
  // 之所以 len- zeroLength 是因为后边添加了0,所以要减去0的长处
  for (let index = 0; index < len - zeroLenght; index++) {
    if (arr[index] === 0) {
      // 这是一个内部循环，用于将当前零元素后的所有元素向前移动一位，覆盖当前的零元素
      // 这样做是为了确保零元素被移到数组末尾后，其余非零元素的相对顺序不变
      for (let j = index; j < len - 1; j++) {
        arr[j] = arr[j + 1];
      }
      // 将数组末尾的元素设置为零，将零元素移到数组末尾
      arr[len - 1] = 0;
      // 将外部循环的索引 index 减一，以便在移动零元素后重新检查当前位置，确保连续的零元素也被移动到末尾
      // 这个0 后边可能是一个连续的0,所以0后续元素向前移动之后,要重新开始从这个位置检查确保连续的O也被移动到末尾
      index--;
      zeroLenght++;
    }
  }
  return arr;
};

const moveZero1 = (arr: Array<number>) => {
  const len = arr.length;
  if (len === 0) return;
  // 数组中0元素的长度
  let zeroLenght: number = 0;
  // 之所以 len- zeroLength 是因为后边添加了0,所以要减去0的长处
  // for循环的时间复杂度是O(n),加上里面的splice,这个算法的时间复杂度是O(n^2)
  for (let index = 0; index < len - zeroLenght; index++) {
    if (arr[index] === 0) {
      // 1.向元素组中末尾添加元素0
      arr.push(0);
      // 2.截取掉之前的0
      arr.splice(index, 1); // splice的时间复杂度本身就是O(n)
      // 3. 将循环索引 index 减一，以便在移除零元素后重新检查当前位置，确保连续的零元素也被移动到末尾
      index--;
      zeroLenght++;
    }
  }
  return arr;
};
// const arr = [1, 0, 1, 1, 4, 0, 0, 2];

const moveZero2 = (arr: Array<number>) => {
  const length = arr.length;
  if (length === 0) return;
  // 这行声明了两个变量 i 和 j，分别用于追踪非零元素和零元素的位置。i 初始值为 0，表示指向第一个非零的数
  let i = 0,
    j = -1;

  for (i = 0; i < length; i++) {
    // 如果当前元素是零，并且之前没有找到过零元素（即 j 仍为 -1），则将 j 设置为当前位置 i，表示找到了第一个零元素的位置
    if (arr[i] === 0 && j <= 0) {
      j = i;
    }
    // 如果当前元素不是零，并且已经找到了第一个零元素
    // 交换当前非零元素和第一个零元素的位置。这样做可以将当前非零元素移到第一个零元素的位置上
    if (arr[i] !== 0 && j >= 0) {
      // 交换元素
      [arr[i], arr[j]] = [arr[j], arr[i]];
      // 将 j 后移一位，指向下一个零元素的位置。这样可以确保在下一次循环中，非零元素可以被移动到下一个零元素的位置上
      j++;
      console.log(arr)
    }
  }
  return arr;
};
moveZero2(arr)
// console.log(moveZero2(arr));
